1. Field of the Invention
The present invention relates to apparatus and a method for direct sampling of traffic in a packet switching network, and, more particularly, to such a method and apparatus for providing “trajectory sampling” or direct sampling of packet data at network traffic points, for example, at packet routers and links in a packet switching network.
2. Description of the Related Arts
Over the years, switched circuit network traffic engineering has become a well known art comprising the steps of measuring traffic over switched circuits in the form of conversation seconds and numbers of calls over periods of time, applying the results to certain probabilistically determined tables, and then installing appropriate facilities and resources in the switched circuit network to match the measured and expected demand. For example, a level of measured traffic over time in a given route between San Francisco and Los Angeles, Calif. is measured and provided to traffic engineers. The traffic engineers then apply a forecasting model to predict the number of circuits required to meet expected demand, and the facilities and resources are routinely provided to meet the expected demand as a function of the telephone company's ability to install and provision the new circuit facilities and resources.
In a packet data telecommunications switching network, these historic approaches cannot be applied because a packet at a point of entry in the network, denoted herein an ingress node, can take any number of possible routes to reach its destination. Moreover, packet switching networks typically provide for duplication of a packet, for example, for multicasting, so that a packet upon network entry is duplicated and delivered to multiple points of egress, each denoted herein an egress node. Moreover, a packet may be lost in a network, never reaching its destination due to expiration of its time to live. There remains a need in the art for improved methods of measuring traffic in a packet switching network, for example, the Internet, a local or wide area data network, an asynchronous transmission mode (ATM) network, cell relay or frame relay network or other types of packet switching networks so that an appropriate number of resources may be determined and provisioned consistent with the result of prior art techniques.
Clearly, the efficiency of resource allocation and the quality of service provided by such packet switching networks, including the Internet, depends critically on effective traffic management. Traffic management consists of short-term traffic control and longer-term traffic engineering. Traffic control operates on a time-scale of seconds and without direct human intervention. Examples of traffic control functions include congestion control, automatic recovery in case of link or router failures, or admission control. Traffic engineering operates on time-scales from minutes to weeks or months, and typically with some degree of human intervention. The goal of traffic engineering in either a packet switching network environment or a switched circuit network environment is the same, to optimally allocate network resources, such as link capacity and router capacity, to different classes of network traffic in order to ensure good service quality and high network efficiency. Examples of traffic engineering functions include traffic characterization (e.g., trending), accounting (e.g., for pricing), and capacity planning and provisioning.
All of these traffic management functions represent feedback loops on a wide range of time-scales and of varying spatial extent, and traffic observation or measurement is therefore an integral component of these functions. The importance of traffic measurement capabilities is compounded by the fact that packet networks such as IP networks do not maintain per-flow state. By contrast, in circuit-switched networks, the traffic is essentially “observable for free”, because per-call state exists along each node on the call's path. In a sense, the scalability of the stateless IP networks has been bought at the expense of observability.
Virtually all traffic control and traffic engineering functions, such as route optimization or planning of failover strategies, rely on an understanding of the spatial flow of traffic through the measurement domain. For example, suppose we observe that some link in the backbone network portion of an overall packet switching network is overloaded. Appropriate corrective action requires an understanding of which ingress nodes the packet traffic observed on this link originates and where it is headed, what customers are affected by the congestion, and what the traffic mix is. Without this information, effective remedies (e.g., rerouting of part of that traffic) cannot be taken.
Also, it should be possible to infer what fraction of traffic entering the measurement domain at a certain ingress node traverses each link in the network, for example to focus on how the traffic of a specific customer flows through the domain, and to diagnose which link might be the reason for a performance problem experienced by that customer. Domain-wide spatial traffic information is also a prerequisite for the establishment of label-switched tunnels, or to decide which potential ingress point is best to connect a new customer to the domain.
We distinguish between direct and indirect measurement methods. Conceptually, an indirect measurement method relies on a network model and network status information to infer the spatial flow of traffic through the domain. For example, suppose that the traffic is observed only at network ingress points (e.g., by computing statistics on the distribution of source-destination pairs). In order to infer how that traffic flows through the domain, timely and accurate information about the state of the routing protocol and link states has to be available. If assumptions about traffic routing have to be made in order to obtain the traffic flow matrix, then the use of an outdated routing table can lead to erroneous inferences, and suboptimal allocation of network resources.
More generally, indirect measurement methods suffer from the uncertainty associated with the physical and logical state of a large, heterogeneous network. This uncertainty has several sources. First, the exact behavior of a network element, such as a router, is not exactly known to the service provider and depends on vendor-specific design choices. For example, the algorithm for traffic splitting among several shortest paths in OSPF is not standardized. Second, there are deliberate sources of randomness in the network to avoid accidental synchronization, e.g., through active queue management disciplines or randomized timers in routing protocols. Third, some of the behavior of the network depends on events outside of the control of the domain; for example, how traffic is routed within an autonomous system (AS) depends in part on the dynamics of route advertisement to this AS by neighboring domains. Fourth, the interaction between adaptive schemes operating at different time-scales and levels of locality (e.g., quality of service (QoS) routing, end-to-end congestion control) may simply be too complex to characterize and predict. Finally, with increasing size and complexity, the likelihood increases for faults and misconfigurations to disrupt the normal operation of the network. Often, traffic measurement is one of the potential tools to detect and diagnose such problems; however, this benefit is mitigated if traffic measurement requires correct network operation.
A direct method does not rely on a network model and an estimation of its state and its expected behavior. Rather, it relies on direct observation of traffic at multiple points in the network. As such, it does not suffer from the sources of uncertainty discussed above. In this paper, we describe a direct method for traffic measurement, called trajectory sampling. The method samples packets that traverse each link (or a subset of these links) within a measurement domain. The subset of sampled packets over a certain period of time can then be used as a representative of the overall traffic.
Sampling has been proposed as a method to measure the end-to-end performance of individual flows in connection-oriented packet switching networks such as asynchronous transfer mode networks (ATM). It is known, for example, to sample ATM cells at the ingress and egress points of a virtual circuit in order to measure QoS metrics such as the end-to-end delay and the loss rate. To compute these metrics, cells at the ingress and egress points have to be matched with one another. Clearly, the technique is limited in terms of the data that can be obtained if only the ingress and egress points are utilized although the concept of utilizing a sample function at a point of ingress in a packet switching network is suggested.
There remains a need in the art for a direct sampling technique for a packet switching network which is considerably more flexible and has a greater range of applications than those described by the prior art.